/*
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出格式：
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1*/
//
// Created by DDD on 2023/11/4.
//

#include <iostream>

using namespace std;
const int Max = 1e5 + 10;
struct Node
{
    int data;
    int ad;
    int next;
} list[Max], ans[Max];
int main()
{
    int headad, n;
    int num;
    cin >> headad >> n;
    for (int i = 0; i < n; i++)
    {

        cin >> num;
        cin >> list[num].data >> list[num].next;
    }
    int count = 1;
    while (headad != -1)
    {
        ans[count].ad = headad;
        ans[count++].data = list[headad].data;
        // printf("f=%05d\n",count);
        headad = list[headad].next;
    }
    for (int i = 1; i < count; i++)
    {

        if (i % 2 == 1)
        {
            list[i] = ans[count - 1 - i / 2];
        }
        else
        {
            list[i] = ans[i / 2];
        }
    }
    for (int i = 1; i < count - 1; i++)
    {

        printf("%05d %d %05d\n", list[i].ad, list[i].data, list[i + 1].ad);
    }
    printf("%05d %d -1\n", list[count - 1].ad, list[count - 1].data);
    return 0;
}
